//
// Created by f12160c on 2018/6/13.
//

#include <iostream>
#include <vector>

using namespace std;

namespace LearnAlgorithm {
    template <typename T>
    void swap_var(T& a, T& b)
    {
        T tmp = a;
        a = b;
        b = tmp;
    }

    vector<int> DirectInsertSorting(vector<int>& input, true_type)
    {
        auto & ret = input;
        int i, j;
        int tmp;
        if(input.size() == 0)
        {
            return ret;
        }
        ret[0] = input[0];
        for(i = 1; i < input.size(); i++)
        {
            tmp = input[i];
            for(j = 0; j < i; j++)
            {
                if(ret[j] > tmp ) {
                    swap_var(ret[j], tmp);
                }
            }
            ret[j] = tmp;
        }
        return ret;
    }

    vector<int> DirectInsertSorting(vector<int>& input, false_type)
    {
        vector<int> ret(input.size());
        int i, j;
        int tmp;
        if(input.size() == 0)
        {
            return ret;
        }
        ret[0] = input[0];
        for(i = 1; i < input.size(); i++)
        {
            tmp = input[i];
            for(j = 0; j < i; j++)
            {
                if(ret[j] > tmp ) {
                    swap_var(ret[j], tmp);
                }
            }
            ret[j] = tmp;
        }
        return ret;
    }
}
